/**
 *  @file MergeDecreasingReuseHead.c
 *  @desc TODO 描述该文件的功能
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-07 10:17
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
}node, *link;

// 创建一个带指定值的新结点
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;  // 内存分配失败
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void initNode(link *head) {
    link node = (link) malloc(sizeof(node));
    if (node == NULL) return;
    node->data = 0;
    node->next = NULL;
    *head = node;
}

// 尾部插入
void insertTail(link head, int value) {
    link node = createNode(value);
    if (node == NULL) return;
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = node;
}

// 打印节点
void printList(link head) {
    if (head == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 反转链表（带头结点）
link reverseList(link head) {
    link cur = head->next;
    link prev = NULL;

    while (cur) {
        link next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    // 构建新链表头结点，复用原头
    head->next = prev;
    return head;
}

// 合并两个升序链表为一个降序链表（复用节点）
link mergeDecreasingReuse(link l1, link l2) {
    if (!l1 || !l2) return NULL;

    link p1 = l1->next;
    link p2 = l2->next;

    link result = (link)malloc(sizeof(node));
    if (!result) return NULL;
    result->next = NULL;

    // 先合并成一个升序链表（尾插法）
    link tail = result;

    while (p1 && p2) {
        if (p1->data <= p2->data) {
            link next = p1->next;
            tail->next = p1;
            p1->next = NULL;
            tail = p1;
            p1 = next;
        } else {
            link next = p2->next;
            tail->next = p2;
            p2->next = NULL;
            tail = p2;
            p2 = next;
        }
    }

    while (p1) {
        link next = p1->next;
        tail->next = p1;
        p1->next = NULL;
        tail = p1;
        p1 = next;
    }

    while (p2) {
        link next = p2->next;
        tail->next = p2;
        p2->next = NULL;
        tail = p2;
        p2 = next;
    }

    free(l1);
    free(l2);

    // 反转链表，得到降序链表
    return reverseList(result);
}



int main() {
    link head;
    initNode(&head);
    insertTail(head, 1);
    insertTail(head, 2);
    insertTail(head, 3);

    link head1;
    initNode(&head1);
    insertTail(head1, 1);
    insertTail(head1, 2);
    insertTail(head1, 3);
    link result = mergeDecreasingReuse(head, head1);
    if (result != NULL) {
        printList(result);
    } else {
        printf("NO RESULT");
    }
}
